Section: New Results

Community detection: dynamic and overlapping

Overlapping community detection is a popular topic in complex networks. Comparing to disjoint community structure, overlapping community structure is more reasonable to describe networks at a macroscopic level. Overlaps shared by communities play an important role in combining different communities. We propose two different approaches to detect overlaps: fuzzy community detection and overlapping community detection. The former estimates membership degree of node belonging to community, and the latter allows node to be shared by communities. In this paper, a fuzzy detection and a clique optimization are introduced. Experimental studies in synthetic networks show fuzzy detection yields meaningful information in stability and hierarchy of communities. And clique optimization is efficient in capturing overlapping nodes. Applications in real networks whose community structure is not well-known find that overlapping clusters found by our fuzzy detection can provide different views than general overlapping nodes in characterize overlaps.

Although community detection has drawn tremendous amount of attention across the sciences in the past decades, no formal consensus has been reached on the very nature of what qualifies a community as such. We take an orthogonal approach by introducing a novel point of view to the problem of overlapping communities. Instead of quantifying the quality of a set of communities, we choose to focus on the intrinsic community-ness of one given set of nodes. To do so, we propose a general metric on graphs, the cohesion, based on counting triangles and inspired by well established sociological considerations. The model has been validated through a large-scale online experiment called Fellows in which users were able to compute their social groups on Face- book and rate the quality of the obtained groups. By observing those ratings in relation to the cohesion we assess that the cohesion is a strong indicator of users subjective perception of the community-ness of a set of people.